/*************************************************************************
	> File Name: priorityqueue.c
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2020年12月03日 星期四 23时47分39秒
 ************************************************************************/
#include <stdlib.h>
#include "priorityqueue.h"

PriQue *initPriQue(int size) {
    PriQue *pq = (PriQue *)malloc(sizeof(PriQue));
    pq->data = (int *)malloc(sizeof(int) * (size + 1));
    pq->cnt = 0;
    pq->size = size;
    return pq;
}

int isEmptyPriQue(PriQue *q) {
    return q->cnt == 0;
}

int topPriQue(PriQue *q) {
    return q->data[1];
}

int pushPriQue(PriQue *q, int val) {
    if (q == NULL) return 0;
    if (q->cnt == q->size) return 0;
    q->data[++(q->cnt)] = val;
    int ind = q->cnt;
    //大顶堆
    while (ind >> 1 && q->data[ind] > q->data[ind >> 1]) {
        swap(q->data[ind], q->data[ind >> 1]);
        ind >>= 1;
    }
    return 1;
}

int popPriQue(PriQue *q) {
    if (q == NULL) return 0;
    if (isEmptyPriQue(q)) return 0;
    q->data[1] = q->data[q->cnt--];
    int ind = 1;
    while ((ind << 1) <= q->cnt) {
        int temp = ind, l  = ind << 1, r = ind << 1 | 1;
        if (q->data[l] > q->data[temp]) temp = l;
        if (r <= q->cnt && q->data[r] > q->data[temp]) temp = r;
        if (temp == ind) break;
        else swap(q->data[ind], q->data[temp]);
        ind = temp;
    }
}

void clearPriQue(PriQue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}
